package syf.tree;

public class ClueBinaryTree {
    public static void main(String[] args) {
        ClueHeroNode root=new ClueHeroNode(1,"lisi");
        ClueHeroNode node2=new ClueHeroNode(2,"wangwu");
        ClueHeroNode node3=new ClueHeroNode(3,"songyf");
        ClueHeroNode node4=new ClueHeroNode(4,"zhangsan");
        ClueHeroNode node5=new ClueHeroNode(5,"cqust");
        ClueHeroNode node6=new ClueHeroNode(6,"cqupt");
        ClueClueBinaryTr clueBinaryTr=new ClueClueBinaryTr(root);
        root.setRight(node3);
        node3.setLeft(node6);
        root.setLeft(node2);
        node2.setLeft(node4);
        node2.setRight(node5);

//        clueBinaryTr.midCluing();
//        System.out.println("===============");
//        System.out.println(node5.getRight());
        System.out.println("===============");
        //前序线索化
        clueBinaryTr.preCluing();
        clueBinaryTr.preClueShow();
//        System.out.println(node5.getRight());
        System.out.println("===============");
        //使用线索化后，不能使用之前的遍历 中序
//        clueBinaryTr.preClueShow();
        System.out.println("===============");
        //后续线索化
//        clueBinaryTr.lastCluing();
//        System.out.println(node6.getRight());
//        clueBinaryTr.lastClueShow();
    }
}
/**
 * 二叉树
 */
class ClueClueBinaryTr {
    private ClueHeroNode root;
    //为实现线索化，需要创建要给指向当前节点的前驱结点的指针 pre总是保留前一个节点
    private ClueHeroNode pre=null;
    public ClueClueBinaryTr(ClueHeroNode root) {
        this.root = root;
    }


    public void preCluing(){
        preCluing(root);
    }
    //前序线索化
    public void preCluing(ClueHeroNode heroNode){
        //如果当前为空直接返回
        if (heroNode==null){
            return;
        }else {
            //对当前的节点设置前驱节点
            if (heroNode.getLeft() == null) {
                heroNode.setLeft(pre);
                heroNode.setLeftType(1);
            }
            //对当前的节点设置后继节点，但是
            if (pre != null && pre.getRight() == null&&pre.getLeft()!=heroNode) {
                pre.setRight(heroNode);
                pre.setRightType(1);
            }
            //将当前节点设置成下一个节点的前驱节点
            pre = heroNode;
            //向左递归，找到最左边的
            if (heroNode.getLeftType() != 1) {
                preCluing(heroNode.getLeft());
            }
            //右递归,这里不能用if判断，否则最后一个值进不去递归
            preCluing(heroNode.getRight());
        }
    }

    public void midCluing(){
        midCluing(root);
    }
    //中序线索化
    public void midCluing(ClueHeroNode heroNode){
        //如果当前为空直接返回
        if (heroNode==null){
            return;
        }else {
            //向左递归，找到最左边的
            midCluing(heroNode.getLeft());
            //对当前的节点设置前驱节点
            if (heroNode.getLeft()==null){
                heroNode.setLeft(pre);
                heroNode.setLeftType(1);
            }
            //对当前的节点设置后继节点，但是当前不能设置，只有当当前节点的下一节点时，吧现在的节点设置为下一节点的前驱节点
            if (pre!=null&&pre.getRight()==null){
                pre.setRight(heroNode);
                pre.setRightType(1);
            }
            //将当前节点设置成下一个节点的前驱节点
            pre=heroNode;
            //向右递归，找到最右边的
            midCluing(heroNode.getRight());
        }
    }

    public void lastCluing(){
        lastCluing(root);
    }
    //后序线索化
    public void lastCluing(ClueHeroNode heroNode){
        //如果当前为空直接返回
        if (heroNode==null){
            return;
        }else {
            //向左递归，找到最左边的
            lastCluing(heroNode.getLeft());
            //向右递归，找到最右边的
            lastCluing(heroNode.getRight());
            //为当前节点设置前驱节点
            if (heroNode.getLeft()==null){
                heroNode.setLeft(pre);
                heroNode.setLeftType(1);
            }
            //对当前的节点设置后继节点，但是当前不能设置，只有当当前节点的下一节点时，吧现在的节点设置为下一节点的前驱节点
            if (pre!=null&&pre.getRight()==null){
                pre.setRight(heroNode);
                pre.setRightType(1);
            }
            //对当前的节点设置前驱节点
            pre=heroNode;
        }
    }

    //前序遍历线索化二叉树
    public void preClueShow(){
        //暂时的中间节点
        ClueHeroNode heroNode=root;
        if (heroNode!=null){
            //和之前定义的有关，当type为0时代表的是没有线索化的子树
            //找到要输出的
            System.out.println(heroNode);
            while (heroNode.getLeftType()==0){
                heroNode=heroNode.getLeft();
                System.out.println(heroNode);
            }
            while (heroNode.getRightType()==1){
                heroNode=heroNode.getRight();
                System.out.println(heroNode);
            }
            System.out.println(heroNode.getLeft());
        }
    }
    //中序遍历线索化二叉树
    public void midClueShow(){
        //暂时的中间节点
        ClueHeroNode heroNode=root;
        while (heroNode!=null){
            //和之前定义的有关，当type为0时代表的是没有线索化的子树
            while (heroNode.getLeftType()==0){
                heroNode=heroNode.getLeft();
            }
            //找到要输出的
            System.out.println(heroNode);
            while (heroNode.getRightType()==1){
                heroNode=heroNode.getRight();
                System.out.println(heroNode);
            }
            heroNode=heroNode.getRight();
        }
    }

    //后序遍历线索化二叉树（有问题）
    public void lastClueShow(){
        //暂时的中间节点
        ClueHeroNode heroNode=root;
        while (heroNode!=null){
            //和之前定义的有关，当type为0时代表的是没有线索化的子树
            while (heroNode.getLeftType()==0){
                heroNode=heroNode.getLeft();
            }
            while (heroNode.getRightType()==1){
                heroNode=heroNode.getRight();
                System.out.println(heroNode);
            }
            //找到要输出的
            System.out.println(heroNode);
            heroNode=heroNode.getRight();
        }
    }

}
/**
 * 英雄节点
 */
class ClueHeroNode{
    private Integer no;
    private String name;
    private ClueHeroNode left;//默认为空
    private ClueHeroNode right;//默认为空
    //说明
    //1、如果leftType == 0,表示指向的是左子树，如果1则表示指向的是前驱节点
    //1、如果rightType == 0,表示指向的是右子树，如果1则表示指向的是前驱节点
    private int leftType;
    private int rightType;

    public int getLeftType() {
        return leftType;
    }

    public void setLeftType(int leftType) {
        this.leftType = leftType;
    }

    public int getRightType() {
        return rightType;
    }

    public void setRightType(int rightType) {
        this.rightType = rightType;
    }

    public ClueHeroNode(Integer no, String name) {
        this.no = no;
        this.name = name;
    }

    public Integer getNo() {
        return no;
    }

    public void setNo(Integer no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public ClueHeroNode getLeft() {
        return left;
    }

    public void setLeft(ClueHeroNode left) {
        this.left = left;
    }

    public ClueHeroNode getRight() {
        return right;
    }

    public void setRight(ClueHeroNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "ClueHeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }
}
